package com.cat.dataStructure03;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/
 * @create 2025/11/15 17:31
 * @since JDK17
 */

public class Solution60 {
    boolean check(int[] price, int k, int target) {
        int last = price[0], cnt = 1, n = price.length;
        for (int i = 1; i < n; i++) {
            if (price[i] - last >= target) {
                cnt++;
                last = price[i];
            }
            if (cnt >= k) {
                return true;
            }
        }

        return false;
    }

    public int maximumTastiness(int[] price, int k) {
        int n = price.length, l = -1, r = 0, mid;
        for (var x : price) {
            r = Math.max(r, x + 1);
        }
        Arrays.sort(price);
        while (l + 1 < r) {
            mid = l + (r - l) / 2;
            if (check(price, k, mid)) { // 可以满足
                l = mid;
            } else {
                r = mid;
            }
        }

        return l;
    }
}
